public class Solution {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 根据一棵树的前序遍历与中序遍历构造二叉树
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int begin, int end) {
        if (begin > end) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findRootIndex(inorder,begin,end,preorder[preIndex]);
        if (rootIndex == -1) {
            return null;
        }

        preIndex++;

        root.left = buildTreeChild(preorder,inorder,begin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,end);

        return root;
    }
    private int findRootIndex(int[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    // 根据一棵树的后序遍历与中序遍历构造二叉树
    public int postIndex;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild2(postorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild2(int[] postorder, int[] inorder, int begin, int end) {
        if (begin > end) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]);

        int rootIndex = findRootIndex2(inorder,begin,end,postorder[postIndex]);
        if (rootIndex == -1) {
            return null;
        }

        postIndex--;

        root.right = buildTreeChild2(postorder,inorder,rootIndex+1,end);
        root.left = buildTreeChild2(postorder,inorder,begin,rootIndex-1);

        return root;
    }
    private int findRootIndex2(int[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    //二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append('(');
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(')');
        }else {
            if (root.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        if (root.right != null) {
            stringBuilder.append('(');
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(')');
        }else {
            return;
        }
    }
}
